In natural language understanding, computerized language systems attempt to identify a logical representation for a text string. In some systems, the representation is a syntactic or grammar-based representation and is formed by performing a syntactic parse of the text.
In many systems, the logical representation takes the form of a sentence tree structure that has the words of the text as leaves and nodes arranged as branches in the tree. An example sentence tree structure is given in FIG. 6i. 
Many different types of parsers have been created. The goal of all parsers is to access a new or unseen utterance and create the logical representation of the utterance.
CFG Parsers
In one type of parser, hand written rules are created that describe how words can be joined together to form phrases and sub-phrases. Additional rules describe how phrases can be joined into larger phrases and sentences. An utterance is parsed by finding one or more words that match one of the rules and linking them together. This process is repeated until all words have been matched to rules. The words are thus grouped together into sub-phrases. The sub-phrases are then grouped together into phrases. Each time a rule is applied to group words and/or phrases, a new node is created that contains the elements that are grouped. Ultimately all words and phrases are grouped into a single node that represents the entire utterance. The term Context Free Grammar (CFG) has been used to describe such a system of rules for parsing.
Dependency Link Parsers
Another type of parser involves hand written rules that describe what words can be linked to other words. These links are formed between words which are dependent on each other in some form. For example in the phrase “the dog”, the word ‘the’ is said to be dependent on ‘dog’. This dependent relationship indicates that ‘the’ in some way modifies ‘dog’. Further examples are the phrases “that dog”, or “Jim's dog”. In these phrases, ‘that’ and ‘Jim's’ are dependent on ‘dog’ and each modify ‘dog’ in some way.
These dependent links can be found between all words of an utterance. All words of an utterance are contained in one or more of these dependent relationships. In each of these dependency links, one word is dependent on the other. The dependent word can come before or after the word it depends on. When an utterance is parsed with this type of parse, a single word is said to be the head of the utterance. All other words in the utterance directly depend on the head word or indirectly depend on the head word by depending on one or more intermediary words that depend on the head word. The term Dependency Grammar has been used to describe such a system for parsing utterances.
CKY Parsers
Another type of parser involves automatically detecting the rules for parsing the utterance. In such a system, there is a training phase and a decoding phase. In the training phase, the rules for parsing an utterance are detected by examining a set of training utterances. The training utterances come from a corpus. Each utterance in the corpus has been labeled to indicate the ideal parse for the utterance. The labels on each utterance indicate which words are grouped into phrases and how the phrases are grouped into the full utterance. These labels in the corpus define the tree structure of each utterance in the corpus. In addition, the labels give a part of speech tag (POS) for each word. For example a word may be a verb, a noun, an adjective or a plurality of other values defined by the conventions of the corpus.
During the training phase, the system collects the labels that indicate how words are grouped into phrases. These labels are converted to a form that is similar to the rules of the hand written rules for the CFG parser. For example a rule found might be that an utterance consists of a noun phrase followed by a verb phrase. Another rule found might be that a noun phrase consists of a determiner followed by a noun as in “the dog”.
Also, the POS tags for each word are collected. A given word may have more than one POS tag. For example the word ‘top’, can be a noun, a verb or an adjective. The training phase collects this information from the corpus and stores it in a data structure that is sometimes called a language model.
When the training phase is completed, the language model is then used during the decoding phase. The decoding phase uses the language model to parse utterances. The parsing process is similar to the process used when applying hand written rules for a CFG. This method of extracting a language model from a corpus and then applying the model to parse utterances is often referred to as supervised parsing. A common type of supervised parsing is a CKY parser.
Common Cover Links
Common Cover Links (CCL) is a type of parser that parses an utterance by creating links between words. FIG. 16 shows an example of an utterance that has been parsed using common cover links. Common cover links are characterized by these attributes:
Each link has a head and a base which are individual words in the utterance.
Each link has a depth value of either 0 or 1.
Each link has can go forward or backward in the utterance.
When a CCL parser is parsing an utterance, it creates links from the current word to words that preceded it in the utterance. Each word may be assigned multiple links.
Ambiguity from Parsing
In all methods of parsing, there is ambiguity. Ambiguity means there are different choices for how an utterance is parsed. One source of ambiguity is in the individual words since a word may have more than one POS tag. When the parser encounters a word that can be either a verb or a noun, the parser must choose which tag is appropriate. The choice then affects which rules can be applied to the word. If the parser chooses verb, then there is a group of rules that apply to verbs. Similarly, there is a group of rules that apply to nouns.
Another source of ambiguity involves how to group phrases into larger phrases. For example, FIG. 8a and FIG. 8b, show alternate ways to attach a prepositional phrase (PP) within the utterance. In FIG. 8a, the PP node 806 is a child of the NP node 804. The PP ‘on whether a . . . ’ is modifying the noun phrase ‘no comment’. In FIG. 8b, the PP node 806 is a child of the VP node 802. The PP ‘on whether a . . . ’ is modifying the verb ‘had’.
All of this ambiguity leads to many different ways that an utterance can be parsed. The parser must choose one parse that is most likely to be the correct parse. One common method of choosing the best parse is to assign a probability value to each possible parse. The best parse is the one that has the highest probability. The probability for a given parse is calculated from the probabilities of each phrase in the parse. Each phrase of the parse gets its probabilities from the words or sub-phrases that linked into it. So each parse for an utterance has a probability that is calculated from each of the words and phrases.
In order for the parser to find the best parse using probabilities, it must find all of the possible parses and calculate the probabilities for each of those parses. An utterance that has N words will have N3 possible parses. So an utterance with 10 words will have 103 or 1000 possible parses.
Terms for the Field
Common Ancestor—In a tree structure, any two nodes will have a common ancestor which is the closest node found going up the tree that is an ancestor to both nodes. For example, in FIG. 6i, the word ‘those’ 616 and the word ‘estimates’ 618 have the NP node 640 as their common ancestor. Similarly, the word ‘lane’ 610 and the word ‘vehemently’ 612 have the node 634 as their common ancestor.
Corpus—A list of utterances that are used for developing and testing a parser. Each utterance has labels that were added by a linguist. The labels give details of the utterance tree structures and also the part of speech tags (POS) for each word in the utterances. A commonly used corpus is the Penn Treebank. This corpus has about 40,000 utterances taken from the Wall Street Journal.
Environment—In linguistics, the environment of a word consists of the words that surround the word in question.
F-Measure—A numeric value that represents the accuracy of a parser. The value of F-Measure ranges from 0 to 100 where 100 represents the best possible result. A parser is evaluated by parsing a block of utterances from the corpus. The results of parsing the utterances are compared with the hand labeled version of the same block of utterances. The F-Measure is computed from this comparison.
Language Model—A data structure used by a parser to store data that was collected from the training corpus during the training phase. The contents of the language model are different for different types of parsers.
Left-most descendent—In a tree structure, a left most descendent for a node is the word that is a descendent of the node and is the furthest left in the utterance. For example, in FIG. 6i, the VP node 636 has a left most descendent of ‘vehemently’ 612. Similarly, the NP node 632, has a left most node of ‘the’ 602.
Parent Node, Child Node—In a tree structure, two nodes are said to be in a parent/child relationship if the child is attached below the parent. For example, in FIG. 8a, the PP node 806 is a child of the NP node 804. The NP node 804 is a parent of the PP node 806.
Utterance—A list of tokens. A token may be one of these, but is not limited to, a word, punctuation or other symbol. An utterance may be one of these, but is not limited to a sentence, question, or sentence fragment.